/*
题目描述：二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

方法：
递归地转换，root的左结点应该替换为root左子树的最大的结点，右节点替换为root右子树的最小的结点

1. 处理左子树
2. 定位左子树形成链表的尾节点
3. 将root加入到链表尾部
4. 处理右子树
5. 连接右子树
 */
public class E36 {
    public static void main(String[] args) {
        TreeNode1 root = new TreeNode1(4);
        root.left = new TreeNode1(2);
        root.right = new TreeNode1(6);
        root.left.left = new TreeNode1(1);
        root.left.right = new TreeNode1(3);
        root.right.left = new TreeNode1(5);
        root.right.right = new TreeNode1(7);

        TreeNode1 res = Convert(root);

        while(res != null){
            System.out.print(res.val + "->");
            res = res.right;
        }
        System.out.println("null");
    }
    //返回的是链表的左节点
    public static TreeNode1 Convert(TreeNode1 pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        if(pRootOfTree.left == null && pRootOfTree.right == null){
            return pRootOfTree;
        }

        TreeNode1 left = Convert(pRootOfTree.left);
        TreeNode1 p = left;
        while(p != null && p.right != null){
            p = p.right;
        }
        if(left != null){
            p.right = pRootOfTree;
            pRootOfTree.left = p;
        }
        TreeNode1 right = Convert(pRootOfTree.right);
        if(right != null){
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left == null ? pRootOfTree : left;
    }
}
/*
1->2->3->4->5->6->7->null
 */